<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 1. 统计和小于目标的下标对数目
        // 时间复杂度：O(nlogn)
        // 空间复杂度：O(1)
        var countPairs = function(nums, target) {
            // sort在不同浏览器实现不同：在chrome V8，是快速排序，是nlogn；
            nums.sort((a, b) => a - b)
            let right = nums.length - 1
            let left = 0
            let ans = 0
            while (left < right) {
                // 如果nums[left]和nums[right]相加比target小，则nums[left]和[left + 1, right - 1]之间的任何数相加都会比target小 => 数组是有序的，和最大的数相加都比targt小了，前面的更满足条件
                if (nums[left] + nums[right] < target) {
                    // 注意不用+1，不包括right本身
                    ans += right - left
                    left++
                } else {
                    // 如果nums[left]和nums[right]相加比target大，则nums[right]和[left + 1, right - 1]之间的任何数相加都会比target大 => 数组是有序的，和最小的数相加都比targt大了，前面的更加不满足条件
                    right--
                }
            }
            return ans
        };
        console.log(countPairs([-1,1,2,3,1], 2));
    </script>
</body>
</html>